/*
题目描述——抽象出模型（用之前学习的是否能解决）
检查
	1.正确性
	2.时间是否会超时。
		c++：1秒大概为10的八次方运算次数
		<10的7次方-10的8次方
		看数据范围判断时间复杂度和大概可能采用什么方法。（手机上）

递归
	自己调用自己
	int f（int n）
	{
		f（n-1）
	}
所有递归——递归搜索树(例如下)
				f(4)
		f(3)			f(2)
	f(2)	f(1)          1
	  1       1
*/

/*
	斐波那契数列——f(n)=f(n-1)+f(n-2)
	1 2 3 5 8 13 21 34 55···
	int main()
	{
	if(n==1) return 1;
	if(n==2) return 2;
	}
*/
#include <stdio.h>
#include <string.h>
#include <stdbool.h>


/*
从1∼n,这n个整数中随机选取任意多个，输出所有可能的选择方案。
*/
/*acwing92T
int f(int n)
{
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	return f(n - 1) + f(n - 2);
}

int main()
{
	int n;
	scanf_s("%d", &n);
	printf("%d", f(n));
	return 0;
}
*/

/*法一
int n;
int st[16];//状态，记录每个位置当前的状态，0表示还没考虑，1表示选它，2表示不选它

void dfs(int u)
{
	if (u > n)
	{
		for (int i = 1; i <= n; ++i)
		{
			if (st[i] == 1)
			{
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}
	st[u] = 2;
	dfs(u + 1);//第一个分支，不选
	st[u] = 0;//恢复现场

	st[u] = 1;
	dfs(u + 1);//第二个分支，选
	st[u] = 0;//
}
int main()
{
	scanf_s("%d", &n);
	dfs(1);
	return 0;
}
*/

/*不会就写递归搜索树
1.依次枚举每个数放哪个位置
2.依次枚举每个位置放哪些数
T94
把 1∼n,这n个整数排成一行后随机打乱顺序，输出所有可能的次序。
*/

int n;
int state[10];//0表示还没放数，1-n表示放了哪个数。长度为N的数组存放数
bool used[10];//true表示用过，false表示还没用过

void dfs(int u)
{
	if (u > n)//边界
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d ", state[i]);//打印方案
		}
		printf("\n");
		return;
	}

	//依次枚举每个分支，即当前位置可以填哪些数
	for (int i = 1; i <= n; i++)
	{
		if (!used[i])
		{
			state[u] = i;
			used[i] = true;
			dfs(u + 1);

			state[u] = 0;//恢复现场，去的什么样，回来就什么样
			used[i] = false;//同上
		}
	}
}

int main()
{
	scanf("%d", &n);
	dfs(1);
	return 0;
}
